lib/Mi manual de algoritmos/version_actual/src/grafos/kruskal.cpp

   1 //Complejidad: O(E log V)
   2 struct edge{
   3   int start, end, weight;
   4   bool operator < (const edge &that) const {
   5     //Si se desea encontrar el árbol de recubrimiento de
   6     //máxima suma, cambiar el < por un >
   7     return weight < that.weight;
   8   }
   9 };
  10
  11
  12 ///////////////// Empieza Union find ////////////////////////
  13 //Complejidad: O(m log n), donde m es el número de operaciones
  14 //y n es el número de objetos. En la práctica la complejidad
  15 //es casi que O(m).
  16 int p[MAXNODES], rank[MAXNODES];
  17 void make_set(int x){ p[x] = x, rank[x] = 0; }
  18 void link(int x, int y){
  19   if (rank[x] > rank[y]) p[y] = x;
  20   else{ p[x] = y; if (rank[x] == rank[y]) rank[y]++; }
  21 }
  22 int find_set(int x){
  23   return x != p[x] ? p[x] = find_set(p[x]) : p[x];
  24 }
  25 void merge(int x, int y){ link(find_set(x), find_set(y)); }
  26 ///////////////// Termina Union find ////////////////////////
  27
  28 //e es un vector con todas las aristas del grafo ¡El grafo
  29 //debe ser no digirido!
  30 long long kruskal(const vector<edge> &e){
  31   long long total = 0;
  32   sort(e.begin(), e.end());
  33   for (int i=0; i<=n; ++i){
  34     make_set(i);
  35   }
  36   for (int i=0; i<e.size(); ++i){
  37     int u = e[i].start, v = e[i].end, w = e[i].weight;
  38     if (find_set(u) != find_set(v)){
  39       total += w;
  40       merge(u, v);
  41     }
  42   }
  43   return total;
  44 }